package cn.edu.leetcode.动态规划;

import java.util.HashMap;

public class 爬楼梯 {
    public static void main(String[] args) {
        System.out.println(climbStairs(15));
        System.out.println(climbStairsDigui(15));
        System.out.println(climbStairsDigui2(15));
    }

    public static int climbStairs(int n) {
        int[] ints = new int[n + 3];
        ints[1] = 1;
        ints[2] = 2;

        for (int i = 3; i <= n; i++) {
            ints[i] = ints[i - 1] + ints[i - 2];
        }

        return ints[n];
    }

    public static int climbStairsDigui(int n) {
        if (n == 1 || n == 2) return n;
        return climbStairsDigui(n - 1) + climbStairsDigui(n - 2);
    }

    static HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

    public static int climbStairsDigui2(int n) {
        if (n == 1 || n == 2) return n;
        int x1, x2;

        if (hashMap.containsKey(n - 1)) {
            x1 = hashMap.get(n - 1);
        } else {
            x1 = climbStairsDigui2(n - 1);
            hashMap.put(n - 1, x1);
        }

        if (hashMap.containsKey(n - 2)) {
            x2 = hashMap.get(n - 2);
        } else {
            x2 = climbStairsDigui2(n - 2);
            hashMap.put(n - 2, x2);
        }

        return x1 + x2;
    }
}
